DDS 0970252 - Autonomous Planning Under Uncertainty
Moshe Rafaeli - moshiktech@gmail.com
Tamir Shazman - tmyr@campus.technion.ac.il
Course website: https://anpl-technion.github.io/Teaching/#POMDP
Course forum and announcements: https://piazza.com/technion.ac.il/fall2025/0970252
Tutorial 1: Foundations of Probability, Bayesian Inference, Environment Representation and Julia¶
Notebook kernel: Julia (recommended version ≥ 1.11)
Packages used (install if needed):
In [1]:
using Pkg
Pkg.add(["Distributions", "LinearAlgebra", "Random", "Statistics", "Plots", "StatsBase", "Combinatorics", "POMDPTools"])
Resolving package versions... No Changes to `C:\Users\moshi\.julia\environments\v1.11\Project.toml` No Changes to `C:\Users\moshi\.julia\environments\v1.11\Manifest.toml`
In [2]:
using LinearAlgebra, Random, Distributions, Statistics, Plots, StatsBase, Combinatorics, POMDPTools
Basic probability - discrete random variables¶
In [3]:
Random.seed!(0970252) # we will use this seed for all random processes in the tutorials
# PMF for biased coin (Heads with prob 0.7)
p_head = 0.7
support = ["H","T"]
pmf = Dict("H"=>p_head, "T"=>1-p_head)
# sample many times and estimate empirical PMF
n = 10000
samples = rand(Binomial(1,p_head), n) # 1 ~ H, 0 ~ T
emp_counts = countmap(samples)
emp_pmf = Dict("H" => emp_counts[1]/n, "T" => emp_counts[0]/n)
# show the true PMF vs the empirical PMF
println("True PMF:\t", pmf)
println("Empirical PMF:\t", emp_pmf)
True PMF: Dict("T" => 0.30000000000000004, "H" => 0.7)
Empirical PMF: Dict("T" => 0.2966, "H" => 0.7034)
Continuous random variables - PDF, sampling, histogram¶
In [4]:
Random.seed!(0970252)
# PDF for Normal distribution
μ, σ = 2.0, 3.0
xs = range(μ-4σ, μ+4σ, length=200)
x_pdf = exp.(-(xs .- μ).^2 ./ (2*(σ^2))) ./ sqrt(2π*(σ^2))
# samples from Normal distribution
rv = Normal(μ, σ)
x_empirical = rand(rv, 10000)
# plot histogram of samples and overlay true PDF
histogram(x_empirical, bins=50, normalize=true, label="empirical")
plot!(xs, x_pdf, label="pdf (Normal)")
Out[4]:
Joint and conditional distributions, marginalization¶
Example: Two Random Variables $X,Y$, with the following joint distribution, and individual distribution:
| $P(X=x,Y=y)$ | $y=0$ | $y=1$ | |
|---|---|---|---|
| $x=0$ | $0.1$ | $0.2$ | $\rightarrow P(X=0)=0.3$ |
| $x=1$ | $0.3$ | $0.4$ | $\rightarrow P(X=1)=0.7$ |
| $\downarrow \\ P(Y=0)=0.4$ | $\downarrow \\ P(Y=1)=0.6$ |
In [5]:
# Example discrete joint distribution for (X,Y)
pXY = Dict( (0,0)=>0.1,
(0,1)=>0.2,
(1,0)=>0.3,
(1,1)=>0.4)
# marginalize to get p(X)
pX = Dict(0 => pXY[(0,0)]+pXY[(0,1)],
1 => pXY[(1,0)]+pXY[(1,1)])
# conditional p(X|Y=1)
pY1 = pXY[(0,1)] + pXY[(1,1)]
pX_given_Y1 = Dict(x => pXY[(x,1)]/pY1 for x in (0,1))
println("P(X) =\t\t", pX)
println("P(X|Y=1) =\t", pX_given_Y1)
P(X) = Dict(0 => 0.30000000000000004, 1 => 0.7) P(X|Y=1) = Dict(0 => 0.3333333333333333, 1 => 0.6666666666666666)
Chain rule and Bayes' rule¶
Example: We have a machine that detects wether a patient is sick.
The patient can either be sick or be healthy, i.e. $X = \{\mathrm{healthy, sick}\}$. The probability of a patient to be sick is 1%.
The machine returns $\mathrm{Positive}$ if it detects the patient is sick or $\mathrm{Negative}$ otherwise, i.e. $Y = \{\mathrm{Positive, Negative}\}$.
The machine returns $\mathrm{Positive}$ 95% of the times when the patient is actually sick, and returns $\mathrm{Positive}$ 3% of the times when the patient is actually healthy.
What is the probability a patient is sick, given the machine returned $\mathrm{Positive}$?
Bayes Rule: $$ \mathbb{P}(\mathrm{sick} \mid \mathrm{Positive}) = \frac{\mathbb{P}(\mathrm{Positive} \mid \mathrm{sick}) \cdot \mathbb{P}(\mathrm{sick})}{\mathbb{P}(\mathrm{Positive})} $$
Marginalization & Chain Rule: $$ \mathbb{P}(\mathrm{Positive}) = \mathbb{P}(\mathrm{Positive, sick}) + \mathbb{P}(\mathrm{Positive, healthy}) = \mathbb{P}(\mathrm{Positive \mid sick}) \cdot \mathbb{P}(\mathrm{sick}) + \mathbb{P}(\mathrm{Positive \mid healthy}) \cdot (1 - \mathbb{P}(\mathrm{sick})) $$
In [6]:
# probabilities for the medical test example
p_sick = 0.01
p_pos_given_sick = 0.95
p_pos_given_healthy = 0.03
# Bayes and Chain rules
p_pos = p_pos_given_sick*p_sick + p_pos_given_healthy*(1-p_sick)
p_sick_given_pos = (p_pos_given_sick * p_sick)/p_pos
println("P ( Sick | Positive ) = ", p_sick_given_pos)
P ( Sick | Positive ) = 0.2423469387755102
Expectation and covariance¶
In [7]:
Random.seed!(0970252)
μ, σ = 1.0, 2.0
# generate samples from Normal distribution
x = rand(Normal(μ, σ), 10000)
E_x = mean(x)
Var_x = var(x)
# generate samples from 2D Gaussian and estimate covariance matrix
μ1, σ1 = 0.0, 1.0
μ2, σ2 = 2.0, 1.5
X = [rand(Normal(μ1, σ1),5000) rand(Normal(μ2, σ2),5000)]
cov_est = cov(X)
println("1D Gaussian: mean = $(μ), variance = $(σ^2)")
println("Empirical mean = $(E_x), Empirical variance = $(Var_x)")
println()
println("2D Gaussian: true means = [$(μ1), $(μ2)], true variances = [$(σ1^2), $(σ2^2)]")
println("Empirical Covariance matrix:\n", repr("text/plain",cov_est))
1D Gaussian: mean = 1.0, variance = 4.0
Empirical mean = 0.9663147301780304, Empirical variance = 3.977300658987374
2D Gaussian: true means = [0.0, 2.0], true variances = [1.0, 2.25]
Empirical Covariance matrix:
2×2 Matrix{Float64}:
1.01026 -0.0392326
-0.0392326 2.29468
Gaussian distributions and information form¶
In [8]:
# Covariance form
μ = [1.0, -0.5]
Σ = [0.5 0.1; 0.1 0.2]
println("Covariance Form:")
println("μ = ", μ)
println("Σ = \n", repr("text/plain",Σ))
Covariance Form:
μ = [1.0, -0.5]
Σ =
2×2 Matrix{Float64}:
0.5 0.1
0.1 0.2
In [9]:
# Information form
Λ = inv(Σ)
η = Λ * μ
println("Information Form:")
println("η = ", η)
println("Λ = \n", repr("text/plain",Λ))
Information Form:
η = [2.7777777777777777, -3.888888888888889]
Λ =
2×2 Matrix{Float64}:
2.22222 -1.11111
-1.11111 5.55556
In [10]:
# back to covariance form
Σ2 = inv(Λ)
μ2 = Σ2 * η
println("Back to Covariance Form:")
println("Recovered μ = ", μ2)
println("Original μ = ", μ)
Back to Covariance Form: Recovered μ = [0.9999999999999998, -0.5] Original μ = [1.0, -0.5]
In [11]:
# PDF for distribution for Covariance form
xs = range(μ[1]-4*Σ[1,1], μ[1]+4*Σ[1,1], length=20)
ys = range(μ[2]-4*Σ[2,2], μ[2]+4*Σ[2,2], length=20)
x_cov_pdf = [exp(-0.5*([x,y]-μ)'*inv(Σ)*([x,y]-μ)) / (2π*sqrt(det(Σ))) for x in xs, y in ys]
x_inf_pdf = [exp(-0.5*([x,y]'*Λ*[x,y] - 2*η'*[x,y] + μ'*Λ*μ)) / (2π*sqrt(det(Σ))) for x in xs, y in ys]
# plot the two PDFs side by side
p1 = plot(xs, ys, x_cov_pdf, linetype=:surface, color=:matter, title="Covariance Form", legend=false)
p2 = plot(xs, ys, x_inf_pdf, linetype=:surface, color=:matter, title="Information Form", legend=false)
plot(p1, p2, layout=(1, 2), size=(800, 400))
Out[11]:
Bayesian Inference - The Tiger Problem¶
The Tiger Problem is a classic example in decision-making under uncertainty. We present now a simplified version of the problem (without rewards or actions).
An agent faces two closed doors: behind one is a tiger, behind the other is treasure. The agent listens to the doors to gather information about the tiger's location.
States ($X$):
- $X = \{\text{tiger-left},\ \text{tiger-right}\}$
Observations ($Z$):
- $Z = \{\text{hear-left},\ \text{hear-right}\}$
The agent listens to the doors and receives an observation $z \in Z$ indicating which door the tiger might be behind, but the observation is noisy.
In [12]:
# The Tiger Problem Example
xs = [:TigerLeft, :TigerRight] # state space
zs = [:HearLeft, :HearRight] # observation space
# NOTE: you can change these parameters to see how the inference changes.
pX = Dict(x=>1/length(xs) for x in xs) # prior P(X) - uniform
pZ_given_X = Dict( :TigerLeft => Dict(:HearLeft=>0.8, :HearRight=>0.2),
:TigerRight => Dict(:HearLeft=>0.3, :HearRight=>0.7) ) # likelihood P(Z|X) - observation model
"""
Perform Bayesian Inference to compute the posterior distribution _P(X|z)_ given:
- `xs`: support of _X_ (discrete and finite)
- `pX`: prior distribution _P(X)_ over the support of _X_ `xs` as a Dictionary, e.g., `pX[x]` = _P(X=x)_
- `pZ_given_X`: likelihood _P(Z|X)_ as a Dictionary of Dictionaries, e.g., `pZ_given_X[x][z]` = _P(Z=z|X=x)_
- `z`: observed value of _Z_
"""
function bayesian_inference(xs, pX, pZ_given_X, z)
# compute p(z)
pz = sum(pZ_given_X[x][z]*pX[x] for x in xs)
# compute p(X|z)
pX_given_z = Dict(x => (pZ_given_X[x][z]*pX[x])/pz for x in xs)
return pX_given_z
end
;
In [13]:
Random.seed!(0970252)
# set the true state of the tiger and the observations, these are unknown to the agent
true_state = :TigerRight
false_state = :TigerLeft
true_observations = :HearRight
false_observations = :HearLeft
println("Initial Probabilities: ", pX)
println()
# Start listening until we are sure where the tiger is
while all(pX[x] < 0.9 for x in xs)
# listen and get observation
z = rand(Binomial(1, pZ_given_X[true_state][true_observations])) == 1 ? true_observations : false_observations
println("Observation: ", z)
# bayesian inference
pX = bayesian_inference(xs, pX, pZ_given_X, z)
println("Probabilities: ", pX)
println()
end
println("True Tiger location:\t", true_state)
println("Agent thinks that:\t", argmax(pX))
Initial Probabilities: Dict(:TigerLeft => 0.5, :TigerRight => 0.5) Observation: HearLeft Probabilities: Dict(:TigerLeft => 0.7272727272727273, :TigerRight => 0.2727272727272727) Observation: HearRight Probabilities: Dict(:TigerLeft => 0.4324324324324325, :TigerRight => 0.5675675675675675) Observation: HearRight Probabilities: Dict(:TigerLeft => 0.17877094972067045, :TigerRight => 0.8212290502793296) Observation: HearRight Probabilities: Dict(:TigerLeft => 0.05855443732845382, :TigerRight => 0.9414455626715462) True Tiger location: TigerRight Agent thinks that: TigerRight
Transition model and observation model - Bayesian update in 1D¶
Example:
Variable $x \in \mathbb{N}$ represents the position of a robot on a 1D line.
The variable changes through time as the robots moves, i.e. $\{ x_0, x_1, x_2, ... \}$.
The robot does not know it's true position, but it maintains a distribution over it's possible position at each time step $t$.
$X_t$ is the random variable representing the position of the robot at time $t$.
The robot has a prior distribution about it's initial position, $\mathbb{P}(X_0)$.
Each time step $t$ the robot moves according to an action $a_t$, which changes it's position at the next time step.
This is the transition model of $X_t$ over time, $\mathbb{P}(X_{t+1} \mid X_{t}, a_{t})$.
After the action is performed and position changed to $x_{t+1}$, the robot gets an observation from it's new position, $z_{t+1}$.
This is the observation model for each time step $t$, $\mathbb{P}(Z_t \mid X_t)$.
The robot uses the observation to update the posterior distribution over it's position, $\mathbb{P}(X_t \mid a_{0:t-1}, z_{1:t})$.
The robot's estimation of it's position at each time $t$ is the Maximum a posteriori (MAP) estimator:
$$ x^*_{t} = \argmax_{x_t} \mathbb{P}(x_t \mid a_{0:t-1}, z_{1:t})$$
In this example we consider:
- Prior distribution: $\mathbb{P}(X_0) \sim \mathcal{U}\{-19,20\}$ (discrete uniform distribution).
- Transition model: $X_{t+1} = X_{t} + a_{t} + \omega_{t}$, where $a_t \in \{-1,+1\}$ and $\omega_{t} = \begin{cases} 0, & \text{w.p.} ~ 0.8 \\ +1, & \text{w.p.} ~ 0.1 \\ -1, & \text{w.p.} ~ 0.1 \\ \end{cases}$, and independent of $X_t$.
- Observation model: $Z_{t} = X_{t} + \nu_{t}$, where $\nu_{t} = \begin{cases} 0, & \text{w.p.} ~ 0.7 \\ +1, & \text{w.p.} ~ 0.15 \\ -1, & \text{w.p.} ~ 0.15 \\ \end{cases}$, and independent of $X_t$.
In [14]:
# Note: you can change these parameters to see how the estimation changes.
x0 = -2 # initial true position
xs = range(-19,20)
pX0 = Dict(x => 1/length(xs) for x in xs) # initial distribution - uniform
w = Dict(0 => 0.8, 1 => 0.1, -1 => 0.1) # motion disturbance
v = Dict(0 => 0.7, 1 => 0.15, -1 => 0.15) # observation noise
get_sample(d) = rand(POMDPTools.SparseCat(keys(d),values(d)))
;
In [15]:
Random.seed!(0970252)
n_steps = 100
controls = [-1, 1] # possible actions of the agent
xt = x0 # true position over time
xt_list = [xt]
pXt = pX0 # distribution over time
est_xt_list = [argmax(pXt)]
println("0: Robot at: ", xt_list[end])
println("0: Estimated position: ", est_xt_list[end])
println()
for t in 1:n_steps
at = rand(controls) # random control
# actual movement
xt += at + get_sample(w)
zt = xt + get_sample(v)
push!(xt_list, xt)
println(t, ": Performed action: ", at)
println(t, ": Robot moved to: ", xt)
println(t, ": Robot observed: ", zt)
# prediction step (perform the action)
pX_pred = Dict{Int, Float64}()
for x in keys(pXt)
for u in keys(w)
x_pred = x + at + u
# Note: if x_pred is not in the keys, get!() creates a new key for it with value 0, then we add the new probability
# if x_pred is already in the keys, get!() returns its current probability value, then we add the new probability
pX_pred[x_pred] = get!(pX_pred, x_pred, 0) + pXt[x]*w[u]
end
end
# compute p(zt)
pzt = 0.0
for x in keys(pX_pred)
for u in keys(v)
if zt == x + u
pzt += pX_pred[x]*v[u]
end
end
end
# update step (inference)
pXt = Dict{Int, Float64}()
for x in keys(pX_pred)
for u in keys(v)
if zt == x + u
# for a specific value x, there is at most one value u that satisfies zt == x + u
pXt[x] = (pX_pred[x]*v[u])/pzt
end
end
end
# MAP estimator
push!(est_xt_list, argmax(pXt))
println(t, ": Estimated position: ", est_xt_list[end])
println()
end
# Calculate RMSE of the MAP estimator
rmse = round(sqrt(mean((xt_list .- est_xt_list).^2)), digits=4)
plot(0:n_steps, xt_list, title="RMSE = $(rmse)", label="True position", xlabel="t", ylabel="position", marker=:circle, markersize=3)
plot!(0:n_steps, est_xt_list, label="MAP position", marker=:square, markersize=3)
0: Robot at: -2 0: Estimated position: -12 1: Performed action: -1 1: Robot moved to: -3 1: Robot observed: -3 1: Estimated position: -3 2: Performed action: 1 2: Robot moved to: -2 2: Robot observed: -2 2: Estimated position: -2 3: Performed action: 1 3: Robot moved to: -1 3: Robot observed: -1 3: Estimated position: -1 4: Performed action: -1 4: Robot moved to: -2 4: Robot observed: -2 4: Estimated position: -2 5: Performed action: 1 5: Robot moved to: -1 5: Robot observed: -1 5: Estimated position: -1 6: Performed action: 1 6: Robot moved to: 0 6: Robot observed: 0 6: Estimated position: 0 7: Performed action: -1 7: Robot moved to: -1 7: Robot observed: -2 7: Estimated position: -1 8: Performed action: 1 8: Robot moved to: -1 8: Robot observed: -2 8: Estimated position: -1 9: Performed action: 1 9: Robot moved to: 0 9: Robot observed: 1 9: Estimated position: 0 10: Performed action: 1 10: Robot moved to: 1 10: Robot observed: 1 10: Estimated position: 1 11: Performed action: 1 11: Robot moved to: 2 11: Robot observed: 1 11: Estimated position: 2 12: Performed action: -1 12: Robot moved to: 0 12: Robot observed: -1 12: Estimated position: 0 13: Performed action: 1 13: Robot moved to: 1 13: Robot observed: 0 13: Estimated position: 0 14: Performed action: -1 14: Robot moved to: 1 14: Robot observed: 0 14: Estimated position: 0 15: Performed action: 1 15: Robot moved to: 2 15: Robot observed: 3 15: Estimated position: 2 16: Performed action: 1 16: Robot moved to: 3 16: Robot observed: 4 16: Estimated position: 3 17: Performed action: -1 17: Robot moved to: 1 17: Robot observed: 1 17: Estimated position: 2 18: Performed action: -1 18: Robot moved to: 0 18: Robot observed: 1 18: Estimated position: 1 19: Performed action: 1 19: Robot moved to: 0 19: Robot observed: 0 19: Estimated position: 1 20: Performed action: 1 20: Robot moved to: 2 20: Robot observed: 2 20: Estimated position: 2 21: Performed action: -1 21: Robot moved to: 1 21: Robot observed: 1 21: Estimated position: 1 22: Performed action: -1 22: Robot moved to: 0 22: Robot observed: 0 22: Estimated position: 0 23: Performed action: 1 23: Robot moved to: 0 23: Robot observed: 0 23: Estimated position: 1 24: Performed action: -1 24: Robot moved to: -1 24: Robot observed: -1 24: Estimated position: -1 25: Performed action: -1 25: Robot moved to: -2 25: Robot observed: -2 25: Estimated position: -2 26: Performed action: 1 26: Robot moved to: -1 26: Robot observed: -1 26: Estimated position: -1 27: Performed action: 1 27: Robot moved to: -1 27: Robot observed: 0 27: Estimated position: 0 28: Performed action: 1 28: Robot moved to: 0 28: Robot observed: 0 28: Estimated position: 1 29: Performed action: 1 29: Robot moved to: 1 29: Robot observed: 1 29: Estimated position: 1 30: Performed action: 1 30: Robot moved to: 2 30: Robot observed: 2 30: Estimated position: 2 31: Performed action: 1 31: Robot moved to: 3 31: Robot observed: 4 31: Estimated position: 3 32: Performed action: -1 32: Robot moved to: 2 32: Robot observed: 2 32: Estimated position: 2 33: Performed action: 1 33: Robot moved to: 3 33: Robot observed: 3 33: Estimated position: 3 34: Performed action: -1 34: Robot moved to: 3 34: Robot observed: 3 34: Estimated position: 2 35: Performed action: -1 35: Robot moved to: 2 35: Robot observed: 2 35: Estimated position: 2 36: Performed action: 1 36: Robot moved to: 3 36: Robot observed: 4 36: Estimated position: 3 37: Performed action: 1 37: Robot moved to: 3 37: Robot observed: 3 37: Estimated position: 4 38: Performed action: -1 38: Robot moved to: 2 38: Robot observed: 2 38: Estimated position: 2 39: Performed action: -1 39: Robot moved to: 0 39: Robot observed: -1 39: Estimated position: 0 40: Performed action: -1 40: Robot moved to: -2 40: Robot observed: -3 40: Estimated position: -2 41: Performed action: -1 41: Robot moved to: -3 41: Robot observed: -4 41: Estimated position: -4 42: Performed action: -1 42: Robot moved to: -4 42: Robot observed: -4 42: Estimated position: -4 43: Performed action: -1 43: Robot moved to: -5 43: Robot observed: -4 43: Estimated position: -5 44: Performed action: -1 44: Robot moved to: -6 44: Robot observed: -6 44: Estimated position: -6 45: Performed action: -1 45: Robot moved to: -7 45: Robot observed: -7 45: Estimated position: -7 46: Performed action: -1 46: Robot moved to: -8 46: Robot observed: -8 46: Estimated position: -8 47: Performed action: 1 47: Robot moved to: -7 47: Robot observed: -7 47: Estimated position: -7 48: Performed action: -1 48: Robot moved to: -8 48: Robot observed: -8 48: Estimated position: -8 49: Performed action: 1 49: Robot moved to: -8 49: Robot observed: -7 49: Estimated position: -7 50: Performed action: 1 50: Robot moved to: -7 50: Robot observed: -7 50: Estimated position: -6 51: Performed action: 1 51: Robot moved to: -6 51: Robot observed: -6 51: Estimated position: -6 52: Performed action: -1 52: Robot moved to: -7 52: Robot observed: -6 52: Estimated position: -6 53: Performed action: 1 53: Robot moved to: -6 53: Robot observed: -6 53: Estimated position: -6 54: Performed action: -1 54: Robot moved to: -7 54: Robot observed: -7 54: Estimated position: -7 55: Performed action: -1 55: Robot moved to: -8 55: Robot observed: -8 55: Estimated position: -8 56: Performed action: 1 56: Robot moved to: -7 56: Robot observed: -7 56: Estimated position: -7 57: Performed action: 1 57: Robot moved to: -7 57: Robot observed: -7 57: Estimated position: -6 58: Performed action: -1 58: Robot moved to: -8 58: Robot observed: -8 58: Estimated position: -8 59: Performed action: -1 59: Robot moved to: -9 59: Robot observed: -8 59: Estimated position: -8 60: Performed action: 1 60: Robot moved to: -8 60: Robot observed: -8 60: Estimated position: -8 61: Performed action: 1 61: Robot moved to: -7 61: Robot observed: -7 61: Estimated position: -7 62: Performed action: 1 62: Robot moved to: -5 62: Robot observed: -4 62: Estimated position: -5 63: Performed action: 1 63: Robot moved to: -4 63: Robot observed: -4 63: Estimated position: -4 64: Performed action: -1 64: Robot moved to: -5 64: Robot observed: -5 64: Estimated position: -5 65: Performed action: 1 65: Robot moved to: -4 65: Robot observed: -4 65: Estimated position: -4 66: Performed action: -1 66: Robot moved to: -5 66: Robot observed: -5 66: Estimated position: -5 67: Performed action: 1 67: Robot moved to: -4 67: Robot observed: -5 67: Estimated position: -4 68: Performed action: -1 68: Robot moved to: -5 68: Robot observed: -5 68: Estimated position: -5 69: Performed action: 1 69: Robot moved to: -4 69: Robot observed: -3 69: Estimated position: -4 70: Performed action: 1 70: Robot moved to: -3 70: Robot observed: -3 70: Estimated position: -3 71: Performed action: -1 71: Robot moved to: -4 71: Robot observed: -4 71: Estimated position: -4 72: Performed action: 1 72: Robot moved to: -3 72: Robot observed: -3 72: Estimated position: -3 73: Performed action: 1 73: Robot moved to: -2 73: Robot observed: -2 73: Estimated position: -2 74: Performed action: 1 74: Robot moved to: -1 74: Robot observed: -1 74: Estimated position: -1 75: Performed action: 1 75: Robot moved to: 1 75: Robot observed: 2 75: Estimated position: 1 76: Performed action: 1 76: Robot moved to: 2 76: Robot observed: 2 76: Estimated position: 2 77: Performed action: 1 77: Robot moved to: 3 77: Robot observed: 3 77: Estimated position: 3 78: Performed action: -1 78: Robot moved to: 2 78: Robot observed: 2 78: Estimated position: 2 79: Performed action: -1 79: Robot moved to: 2 79: Robot observed: 2 79: Estimated position: 1 80: Performed action: 1 80: Robot moved to: 3 80: Robot observed: 2 80: Estimated position: 2 81: Performed action: 1 81: Robot moved to: 4 81: Robot observed: 4 81: Estimated position: 4 82: Performed action: 1 82: Robot moved to: 6 82: Robot observed: 6 82: Estimated position: 5 83: Performed action: -1 83: Robot moved to: 5 83: Robot observed: 5 83: Estimated position: 5 84: Performed action: -1 84: Robot moved to: 4 84: Robot observed: 4 84: Estimated position: 4 85: Performed action: -1 85: Robot moved to: 3 85: Robot observed: 3 85: Estimated position: 3 86: Performed action: 1 86: Robot moved to: 4 86: Robot observed: 4 86: Estimated position: 4 87: Performed action: 1 87: Robot moved to: 5 87: Robot observed: 5 87: Estimated position: 5 88: Performed action: 1 88: Robot moved to: 6 88: Robot observed: 7 88: Estimated position: 6 89: Performed action: 1 89: Robot moved to: 7 89: Robot observed: 7 89: Estimated position: 7 90: Performed action: 1 90: Robot moved to: 8 90: Robot observed: 8 90: Estimated position: 8 91: Performed action: 1 91: Robot moved to: 9 91: Robot observed: 9 91: Estimated position: 9 92: Performed action: -1 92: Robot moved to: 8 92: Robot observed: 9 92: Estimated position: 8 93: Performed action: -1 93: Robot moved to: 8 93: Robot observed: 8 93: Estimated position: 8 94: Performed action: 1 94: Robot moved to: 9 94: Robot observed: 9 94: Estimated position: 9 95: Performed action: 1 95: Robot moved to: 10 95: Robot observed: 10 95: Estimated position: 10 96: Performed action: 1 96: Robot moved to: 11 96: Robot observed: 12 96: Estimated position: 11 97: Performed action: -1 97: Robot moved to: 10 97: Robot observed: 10 97: Estimated position: 10 98: Performed action: 1 98: Robot moved to: 11 98: Robot observed: 11 98: Estimated position: 11 99: Performed action: -1 99: Robot moved to: 11 99: Robot observed: 10 99: Estimated position: 10 100: Performed action: 1 100: Robot moved to: 12 100: Robot observed: 13 100: Estimated position: 12
Out[15]:
Occupancy Grid Map (2D)¶
A 2D occupancy grid map $m = \{ m_{ij} \}$ is a matrix where each element $m_{ij}$ represents the cell $(i, j)$.
The probability that the cell $m_{ij}$ is occupied is defined as $p_{ij}$:
$$
p_{ij} = \mathbb{P}(m_{ij} = 1) = \mathbb{P}(\text{cell } (i,j) \text{ is occupied})
$$
Assuming the cells are independent of each other, the probability of the occupancy map:
$$
\mathbb{P}(m) = \prod_{i,j} \mathbb{P}(m_{ij}) = \prod_{i,j} p_{ij}
$$
In [16]:
Random.seed!(0970252)
map = [
1 1 0 0 0 0 0 0 1 1;
1 0 0 0 1 0 0 0 0 1;
0 0 0 1 0 0 0 0 0 0;
0 0 1 0 0 0 1 1 0 0;
0 0 1 0 0 0 0 0 0 0;
0 0 1 0 0 0 0 0 0 0;
0 0 1 0 0 0 1 1 0 0;
0 0 0 1 0 0 0 0 0 0;
1 0 0 0 1 0 0 0 0 1;
1 1 0 0 0 0 0 0 1 1
]
nx, ny = size(map)
heatmap(map', c=cgrad(:grays, rev=true), title="True Map", xlabel='x', ylabel='y', legend=false, size=(400,400))
Out[16]:
In [17]:
# Observation model of the robot
pzOcc_given_mOcc = 0.9 # P(Z=occupied | cell=occupied)
pzOcc_given_mFree = 0.3 # P(Z=occupied | cell=free)
"""
Perform Bayesian Inference to update the probability of a cell being occupied, based on the given observation.
- `pmOcc`: probability of the cell being occupied
- `z`: observation of the cell (1 = occupied, 0 = free)
"""
function cell_bayesian_inference(pmOcc, z)
if z == 1 # observation is occupied
pz = pzOcc_given_mOcc * pmOcc + pzOcc_given_mFree * (1 - pmOcc)
pmOcc_next = pzOcc_given_mOcc * pmOcc
return pmOcc_next / pz
else # observation is occupied
pz = (1 - pzOcc_given_mOcc) * pmOcc + (1 - pzOcc_given_mFree) * (1 - pmOcc)
pmOcc_next = (1 - pzOcc_given_mOcc) * pmOcc
return pmOcc_next / pz
end
end
"""
Select a random valid next position from the current position (x, y).
Valid moves are within bounds of the map.
If there are no valid moves, stay in the same position.
- `x`, `x`: current position
- `nx`, `ny`: size of the map
"""
function next_position(x, y, nx, ny)
# possible moves: up, down, left, right
moves = [(0,1), (0,-1), (1,0), (-1,0)]
valid_positions = [(x+dx, y+dy) for (dx,dy) in moves if (0 < x+dx <= nx) && (0 < y+dy <= ny)]
return isempty(valid_positions) ? (x, y) : rand(valid_positions)
end
;
In [18]:
Random.seed!(0970252)
# log_odds_map = zeros(nx,ny) # log-odds representation of the occupancy grid, initialized to 0 (p=0.5 for all cells)
prob_map = ones(nx,ny)*0.5 # initialized to p_occupied=0.5 for all cells
robot_pos = (1, 1) # starting position of the robot
n_steps = 1000
anim = @animate for iter in 1:n_steps
# move to a new position
global robot_pos = next_position(robot_pos[1], robot_pos[2], nx, ny)
# simulate observation at the new position, assuming for simplicity the observation is noise free
z = map[robot_pos...]
println("Step ", iter, ": Robot moved to: ", robot_pos, ", observed: ", z == 1 ? "occupied" : "free")
# update probability for the observed cell
prob_map[robot_pos...] = cell_bayesian_inference(prob_map[robot_pos...], z)
# visualize the current distribution of the map
heatmap(prob_map', c=cgrad(:grays, rev=true), title="Map distribution @t=$iter", xlabel='x', ylabel='y', size=(400,400))
scatter!([robot_pos[1]], [robot_pos[2]], markersize=10, markercolor=:red, label="Robot")
end
;
Step 1: Robot moved to: (1, 2), observed: occupied Step 2: Robot moved to: (1, 3), observed: free Step 3: Robot moved to: (1, 4), observed: free Step 4: Robot moved to: (2, 4), observed: free Step 5: Robot moved to: (3, 4), observed: occupied Step 6: Robot moved to: (3, 5), observed: free Step 7: Robot moved to: (2, 5), observed: occupied Step 8: Robot moved to: (2, 6), observed: free Step 9: Robot moved to: (2, 5), observed: occupied Step 10: Robot moved to: (2, 4), observed: free Step 11: Robot moved to: (2, 3), observed: free Step 12: Robot moved to: (2, 4), observed: free Step 13: Robot moved to: (1, 4), observed: free Step 14: Robot moved to: (1, 5), observed: free Step 15: Robot moved to: (1, 6), observed: free Step 16: Robot moved to: (1, 5), observed: free Step 17: Robot moved to: (1, 4), observed: free Step 18: Robot moved to: (1, 5), observed: free Step 19: Robot moved to: (1, 4), observed: free Step 20: Robot moved to: (1, 5), observed: free Step 21: Robot moved to: (2, 5), observed: occupied Step 22: Robot moved to: (3, 5), observed: free Step 23: Robot moved to: (2, 5), observed: occupied Step 24: Robot moved to: (1, 5), observed: free Step 25: Robot moved to: (2, 5), observed: occupied Step 26: Robot moved to: (3, 5), observed: free Step 27: Robot moved to: (2, 5), observed: occupied Step 28: Robot moved to: (3, 5), observed: free Step 29: Robot moved to: (3, 6), observed: free Step 30: Robot moved to: (3, 5), observed: free Step 31: Robot moved to: (2, 5), observed: occupied Step 32: Robot moved to: (2, 4), observed: free Step 33: Robot moved to: (3, 4), observed: occupied Step 34: Robot moved to: (3, 5), observed: free Step 35: Robot moved to: (2, 5), observed: occupied Step 36: Robot moved to: (1, 5), observed: free Step 37: Robot moved to: (2, 5), observed: occupied Step 38: Robot moved to: (3, 5), observed: free Step 39: Robot moved to: (2, 5), observed: occupied Step 40: Robot moved to: (2, 6), observed: free Step 41: Robot moved to: (1, 6), observed: free Step 42: Robot moved to: (2, 6), observed: free Step 43: Robot moved to: (3, 6), observed: free Step 44: Robot moved to: (4, 6), observed: free Step 45: Robot moved to: (3, 6), observed: free Step 46: Robot moved to: (2, 6), observed: free Step 47: Robot moved to: (2, 7), observed: free Step 48: Robot moved to: (1, 7), observed: free Step 49: Robot moved to: (1, 8), observed: free Step 50: Robot moved to: (2, 8), observed: free Step 51: Robot moved to: (3, 8), observed: free Step 52: Robot moved to: (3, 9), observed: free Step 53: Robot moved to: (4, 9), observed: free Step 54: Robot moved to: (3, 9), observed: free Step 55: Robot moved to: (4, 9), observed: free Step 56: Robot moved to: (3, 9), observed: free Step 57: Robot moved to: (3, 8), observed: free Step 58: Robot moved to: (4, 8), observed: occupied Step 59: Robot moved to: (3, 8), observed: free Step 60: Robot moved to: (3, 7), observed: free Step 61: Robot moved to: (3, 6), observed: free Step 62: Robot moved to: (3, 5), observed: free Step 63: Robot moved to: (4, 5), observed: free Step 64: Robot moved to: (4, 6), observed: free Step 65: Robot moved to: (4, 5), observed: free Step 66: Robot moved to: (4, 4), observed: free Step 67: Robot moved to: (5, 4), observed: free Step 68: Robot moved to: (4, 4), observed: free Step 69: Robot moved to: (4, 3), observed: occupied Step 70: Robot moved to: (4, 2), observed: free Step 71: Robot moved to: (5, 2), observed: free Step 72: Robot moved to: (6, 2), observed: free Step 73: Robot moved to: (6, 1), observed: free Step 74: Robot moved to: (6, 2), observed: free Step 75: Robot moved to: (6, 3), observed: occupied Step 76: Robot moved to: (7, 3), observed: occupied Step 77: Robot moved to: (7, 2), observed: free Step 78: Robot moved to: (7, 1), observed: free Step 79: Robot moved to: (6, 1), observed: free Step 80: Robot moved to: (5, 1), observed: free Step 81: Robot moved to: (4, 1), observed: free Step 82: Robot moved to: (5, 1), observed: free Step 83: Robot moved to: (6, 1), observed: free Step 84: Robot moved to: (7, 1), observed: free Step 85: Robot moved to: (6, 1), observed: free Step 86: Robot moved to: (7, 1), observed: free Step 87: Robot moved to: (8, 1), observed: free Step 88: Robot moved to: (7, 1), observed: free Step 89: Robot moved to: (8, 1), observed: free Step 90: Robot moved to: (8, 2), observed: free Step 91: Robot moved to: (7, 2), observed: free Step 92: Robot moved to: (7, 1), observed: free Step 93: Robot moved to: (6, 1), observed: free Step 94: Robot moved to: (6, 2), observed: free Step 95: Robot moved to: (6, 1), observed: free Step 96: Robot moved to: (6, 2), observed: free Step 97: Robot moved to: (7, 2), observed: free Step 98: Robot moved to: (8, 2), observed: free Step 99: Robot moved to: (8, 3), observed: free Step 100: Robot moved to: (8, 2), observed: free Step 101: Robot moved to: (7, 2), observed: free Step 102: Robot moved to: (7, 3), observed: occupied Step 103: Robot moved to: (7, 2), observed: free Step 104: Robot moved to: (6, 2), observed: free Step 105: Robot moved to: (6, 3), observed: occupied Step 106: Robot moved to: (7, 3), observed: occupied Step 107: Robot moved to: (7, 4), observed: free Step 108: Robot moved to: (6, 4), observed: free Step 109: Robot moved to: (7, 4), observed: free Step 110: Robot moved to: (6, 4), observed: free Step 111: Robot moved to: (6, 3), observed: occupied Step 112: Robot moved to: (6, 4), observed: free Step 113: Robot moved to: (6, 3), observed: occupied Step 114: Robot moved to: (6, 2), observed: free Step 115: Robot moved to: (6, 1), observed: free Step 116: Robot moved to: (5, 1), observed: free Step 117: Robot moved to: (4, 1), observed: free Step 118: Robot moved to: (5, 1), observed: free Step 119: Robot moved to: (4, 1), observed: free Step 120: Robot moved to: (3, 1), observed: free Step 121: Robot moved to: (3, 2), observed: free Step 122: Robot moved to: (3, 1), observed: free Step 123: Robot moved to: (2, 1), observed: occupied Step 124: Robot moved to: (2, 2), observed: free Step 125: Robot moved to: (2, 3), observed: free Step 126: Robot moved to: (2, 4), observed: free Step 127: Robot moved to: (2, 3), observed: free Step 128: Robot moved to: (2, 4), observed: free Step 129: Robot moved to: (1, 4), observed: free Step 130: Robot moved to: (1, 5), observed: free Step 131: Robot moved to: (1, 6), observed: free Step 132: Robot moved to: (1, 7), observed: free Step 133: Robot moved to: (1, 6), observed: free Step 134: Robot moved to: (1, 7), observed: free Step 135: Robot moved to: (1, 6), observed: free Step 136: Robot moved to: (1, 5), observed: free Step 137: Robot moved to: (2, 5), observed: occupied Step 138: Robot moved to: (2, 4), observed: free Step 139: Robot moved to: (1, 4), observed: free Step 140: Robot moved to: (1, 5), observed: free Step 141: Robot moved to: (1, 4), observed: free Step 142: Robot moved to: (1, 5), observed: free Step 143: Robot moved to: (2, 5), observed: occupied Step 144: Robot moved to: (3, 5), observed: free Step 145: Robot moved to: (4, 5), observed: free Step 146: Robot moved to: (3, 5), observed: free Step 147: Robot moved to: (2, 5), observed: occupied Step 148: Robot moved to: (3, 5), observed: free Step 149: Robot moved to: (3, 6), observed: free Step 150: Robot moved to: (4, 6), observed: free Step 151: Robot moved to: (5, 6), observed: free Step 152: Robot moved to: (5, 7), observed: free Step 153: Robot moved to: (5, 8), observed: free Step 154: Robot moved to: (5, 7), observed: free Step 155: Robot moved to: (5, 8), observed: free Step 156: Robot moved to: (4, 8), observed: occupied Step 157: Robot moved to: (3, 8), observed: free Step 158: Robot moved to: (3, 9), observed: free Step 159: Robot moved to: (4, 9), observed: free Step 160: Robot moved to: (4, 8), observed: occupied Step 161: Robot moved to: (5, 8), observed: free Step 162: Robot moved to: (5, 7), observed: free Step 163: Robot moved to: (5, 8), observed: free Step 164: Robot moved to: (6, 8), observed: free Step 165: Robot moved to: (6, 7), observed: free Step 166: Robot moved to: (7, 7), observed: occupied Step 167: Robot moved to: (7, 8), observed: occupied Step 168: Robot moved to: (7, 9), observed: free Step 169: Robot moved to: (6, 9), observed: free Step 170: Robot moved to: (5, 9), observed: free Step 171: Robot moved to: (6, 9), observed: free Step 172: Robot moved to: (6, 10), observed: free Step 173: Robot moved to: (7, 10), observed: free Step 174: Robot moved to: (8, 10), observed: free Step 175: Robot moved to: (8, 9), observed: free Step 176: Robot moved to: (8, 10), observed: free Step 177: Robot moved to: (7, 10), observed: free Step 178: Robot moved to: (6, 10), observed: free Step 179: Robot moved to: (6, 9), observed: free Step 180: Robot moved to: (6, 8), observed: free Step 181: Robot moved to: (5, 8), observed: free Step 182: Robot moved to: (4, 8), observed: occupied Step 183: Robot moved to: (4, 9), observed: free Step 184: Robot moved to: (5, 9), observed: free Step 185: Robot moved to: (4, 9), observed: free Step 186: Robot moved to: (3, 9), observed: free Step 187: Robot moved to: (2, 9), observed: free Step 188: Robot moved to: (2, 10), observed: occupied Step 189: Robot moved to: (2, 9), observed: free Step 190: Robot moved to: (2, 10), observed: occupied Step 191: Robot moved to: (2, 9), observed: free Step 192: Robot moved to: (2, 10), observed: occupied Step 193: Robot moved to: (1, 10), observed: occupied Step 194: Robot moved to: (1, 9), observed: occupied Step 195: Robot moved to: (1, 8), observed: free Step 196: Robot moved to: (1, 9), observed: occupied Step 197: Robot moved to: (1, 8), observed: free Step 198: Robot moved to: (1, 7), observed: free Step 199: Robot moved to: (2, 7), observed: free Step 200: Robot moved to: (3, 7), observed: free Step 201: Robot moved to: (4, 7), observed: occupied Step 202: Robot moved to: (4, 8), observed: occupied Step 203: Robot moved to: (5, 8), observed: free Step 204: Robot moved to: (5, 9), observed: free Step 205: Robot moved to: (4, 9), observed: free Step 206: Robot moved to: (4, 10), observed: free Step 207: Robot moved to: (3, 10), observed: free Step 208: Robot moved to: (4, 10), observed: free Step 209: Robot moved to: (5, 10), observed: free Step 210: Robot moved to: (6, 10), observed: free Step 211: Robot moved to: (7, 10), observed: free Step 212: Robot moved to: (7, 9), observed: free Step 213: Robot moved to: (8, 9), observed: free Step 214: Robot moved to: (7, 9), observed: free Step 215: Robot moved to: (8, 9), observed: free Step 216: Robot moved to: (8, 8), observed: free Step 217: Robot moved to: (9, 8), observed: free Step 218: Robot moved to: (9, 7), observed: free Step 219: Robot moved to: (9, 6), observed: free Step 220: Robot moved to: (8, 6), observed: free Step 221: Robot moved to: (8, 7), observed: free Step 222: Robot moved to: (9, 7), observed: free Step 223: Robot moved to: (10, 7), observed: free Step 224: Robot moved to: (9, 7), observed: free Step 225: Robot moved to: (8, 7), observed: free Step 226: Robot moved to: (9, 7), observed: free Step 227: Robot moved to: (9, 6), observed: free Step 228: Robot moved to: (10, 6), observed: free Step 229: Robot moved to: (9, 6), observed: free Step 230: Robot moved to: (9, 7), observed: free Step 231: Robot moved to: (9, 6), observed: free Step 232: Robot moved to: (9, 7), observed: free Step 233: Robot moved to: (10, 7), observed: free Step 234: Robot moved to: (10, 8), observed: free Step 235: Robot moved to: (10, 9), observed: occupied Step 236: Robot moved to: (9, 9), observed: free Step 237: Robot moved to: (9, 10), observed: occupied Step 238: Robot moved to: (8, 10), observed: free Step 239: Robot moved to: (8, 9), observed: free Step 240: Robot moved to: (7, 9), observed: free Step 241: Robot moved to: (6, 9), observed: free Step 242: Robot moved to: (6, 10), observed: free Step 243: Robot moved to: (7, 10), observed: free Step 244: Robot moved to: (8, 10), observed: free Step 245: Robot moved to: (7, 10), observed: free Step 246: Robot moved to: (7, 9), observed: free Step 247: Robot moved to: (7, 8), observed: occupied Step 248: Robot moved to: (8, 8), observed: free Step 249: Robot moved to: (8, 9), observed: free Step 250: Robot moved to: (8, 8), observed: free Step 251: Robot moved to: (9, 8), observed: free Step 252: Robot moved to: (9, 9), observed: free Step 253: Robot moved to: (9, 8), observed: free Step 254: Robot moved to: (9, 9), observed: free Step 255: Robot moved to: (9, 8), observed: free Step 256: Robot moved to: (8, 8), observed: free Step 257: Robot moved to: (9, 8), observed: free Step 258: Robot moved to: (9, 9), observed: free Step 259: Robot moved to: (10, 9), observed: occupied Step 260: Robot moved to: (10, 10), observed: occupied Step 261: Robot moved to: (10, 9), observed: occupied Step 262: Robot moved to: (9, 9), observed: free Step 263: Robot moved to: (9, 8), observed: free Step 264: Robot moved to: (8, 8), observed: free Step 265: Robot moved to: (9, 8), observed: free Step 266: Robot moved to: (10, 8), observed: free Step 267: Robot moved to: (10, 9), observed: occupied Step 268: Robot moved to: (10, 8), observed: free Step 269: Robot moved to: (10, 7), observed: free Step 270: Robot moved to: (10, 8), observed: free Step 271: Robot moved to: (9, 8), observed: free Step 272: Robot moved to: (10, 8), observed: free Step 273: Robot moved to: (10, 7), observed: free Step 274: Robot moved to: (10, 8), observed: free Step 275: Robot moved to: (10, 7), observed: free Step 276: Robot moved to: (9, 7), observed: free Step 277: Robot moved to: (9, 6), observed: free Step 278: Robot moved to: (8, 6), observed: free Step 279: Robot moved to: (9, 6), observed: free Step 280: Robot moved to: (8, 6), observed: free Step 281: Robot moved to: (8, 7), observed: free Step 282: Robot moved to: (8, 8), observed: free Step 283: Robot moved to: (7, 8), observed: occupied Step 284: Robot moved to: (8, 8), observed: free Step 285: Robot moved to: (9, 8), observed: free Step 286: Robot moved to: (10, 8), observed: free Step 287: Robot moved to: (10, 7), observed: free Step 288: Robot moved to: (9, 7), observed: free Step 289: Robot moved to: (9, 8), observed: free Step 290: Robot moved to: (9, 9), observed: free Step 291: Robot moved to: (9, 10), observed: occupied Step 292: Robot moved to: (10, 10), observed: occupied Step 293: Robot moved to: (9, 10), observed: occupied Step 294: Robot moved to: (9, 9), observed: free Step 295: Robot moved to: (9, 10), observed: occupied Step 296: Robot moved to: (8, 10), observed: free Step 297: Robot moved to: (7, 10), observed: free Step 298: Robot moved to: (6, 10), observed: free Step 299: Robot moved to: (6, 9), observed: free Step 300: Robot moved to: (5, 9), observed: free Step 301: Robot moved to: (4, 9), observed: free Step 302: Robot moved to: (3, 9), observed: free Step 303: Robot moved to: (3, 8), observed: free Step 304: Robot moved to: (2, 8), observed: free Step 305: Robot moved to: (2, 9), observed: free Step 306: Robot moved to: (3, 9), observed: free Step 307: Robot moved to: (2, 9), observed: free Step 308: Robot moved to: (2, 8), observed: free Step 309: Robot moved to: (2, 7), observed: free Step 310: Robot moved to: (3, 7), observed: free Step 311: Robot moved to: (4, 7), observed: occupied Step 312: Robot moved to: (3, 7), observed: free Step 313: Robot moved to: (3, 8), observed: free Step 314: Robot moved to: (3, 9), observed: free Step 315: Robot moved to: (4, 9), observed: free Step 316: Robot moved to: (4, 10), observed: free Step 317: Robot moved to: (3, 10), observed: free Step 318: Robot moved to: (4, 10), observed: free Step 319: Robot moved to: (4, 9), observed: free Step 320: Robot moved to: (5, 9), observed: free Step 321: Robot moved to: (6, 9), observed: free Step 322: Robot moved to: (6, 10), observed: free Step 323: Robot moved to: (7, 10), observed: free Step 324: Robot moved to: (8, 10), observed: free Step 325: Robot moved to: (8, 9), observed: free Step 326: Robot moved to: (8, 10), observed: free Step 327: Robot moved to: (8, 9), observed: free Step 328: Robot moved to: (8, 10), observed: free Step 329: Robot moved to: (7, 10), observed: free Step 330: Robot moved to: (7, 9), observed: free Step 331: Robot moved to: (7, 8), observed: occupied Step 332: Robot moved to: (8, 8), observed: free Step 333: Robot moved to: (8, 7), observed: free Step 334: Robot moved to: (8, 8), observed: free Step 335: Robot moved to: (8, 9), observed: free Step 336: Robot moved to: (8, 10), observed: free Step 337: Robot moved to: (7, 10), observed: free Step 338: Robot moved to: (6, 10), observed: free Step 339: Robot moved to: (7, 10), observed: free Step 340: Robot moved to: (8, 10), observed: free Step 341: Robot moved to: (7, 10), observed: free Step 342: Robot moved to: (7, 9), observed: free Step 343: Robot moved to: (6, 9), observed: free Step 344: Robot moved to: (5, 9), observed: free Step 345: Robot moved to: (6, 9), observed: free Step 346: Robot moved to: (6, 10), observed: free Step 347: Robot moved to: (5, 10), observed: free Step 348: Robot moved to: (6, 10), observed: free Step 349: Robot moved to: (7, 10), observed: free Step 350: Robot moved to: (6, 10), observed: free Step 351: Robot moved to: (7, 10), observed: free Step 352: Robot moved to: (7, 9), observed: free Step 353: Robot moved to: (6, 9), observed: free Step 354: Robot moved to: (7, 9), observed: free Step 355: Robot moved to: (6, 9), observed: free Step 356: Robot moved to: (6, 8), observed: free Step 357: Robot moved to: (5, 8), observed: free Step 358: Robot moved to: (5, 7), observed: free Step 359: Robot moved to: (5, 8), observed: free Step 360: Robot moved to: (6, 8), observed: free Step 361: Robot moved to: (6, 9), observed: free Step 362: Robot moved to: (6, 8), observed: free Step 363: Robot moved to: (5, 8), observed: free Step 364: Robot moved to: (5, 7), observed: free Step 365: Robot moved to: (6, 7), observed: free Step 366: Robot moved to: (7, 7), observed: occupied Step 367: Robot moved to: (8, 7), observed: free Step 368: Robot moved to: (8, 8), observed: free Step 369: Robot moved to: (8, 7), observed: free Step 370: Robot moved to: (8, 6), observed: free Step 371: Robot moved to: (7, 6), observed: free Step 372: Robot moved to: (6, 6), observed: free Step 373: Robot moved to: (6, 7), observed: free Step 374: Robot moved to: (7, 7), observed: occupied Step 375: Robot moved to: (7, 6), observed: free Step 376: Robot moved to: (7, 7), observed: occupied Step 377: Robot moved to: (8, 7), observed: free Step 378: Robot moved to: (9, 7), observed: free Step 379: Robot moved to: (9, 8), observed: free Step 380: Robot moved to: (8, 8), observed: free Step 381: Robot moved to: (9, 8), observed: free Step 382: Robot moved to: (9, 7), observed: free Step 383: Robot moved to: (9, 8), observed: free Step 384: Robot moved to: (9, 9), observed: free Step 385: Robot moved to: (10, 9), observed: occupied Step 386: Robot moved to: (10, 10), observed: occupied Step 387: Robot moved to: (9, 10), observed: occupied Step 388: Robot moved to: (10, 10), observed: occupied Step 389: Robot moved to: (10, 9), observed: occupied Step 390: Robot moved to: (10, 10), observed: occupied Step 391: Robot moved to: (9, 10), observed: occupied Step 392: Robot moved to: (10, 10), observed: occupied Step 393: Robot moved to: (9, 10), observed: occupied Step 394: Robot moved to: (9, 9), observed: free Step 395: Robot moved to: (9, 10), observed: occupied Step 396: Robot moved to: (9, 9), observed: free Step 397: Robot moved to: (9, 10), observed: occupied Step 398: Robot moved to: (9, 9), observed: free Step 399: Robot moved to: (9, 10), observed: occupied Step 400: Robot moved to: (8, 10), observed: free Step 401: Robot moved to: (9, 10), observed: occupied Step 402: Robot moved to: (8, 10), observed: free Step 403: Robot moved to: (8, 9), observed: free Step 404: Robot moved to: (7, 9), observed: free Step 405: Robot moved to: (6, 9), observed: free Step 406: Robot moved to: (6, 8), observed: free Step 407: Robot moved to: (5, 8), observed: free Step 408: Robot moved to: (6, 8), observed: free Step 409: Robot moved to: (6, 9), observed: free Step 410: Robot moved to: (7, 9), observed: free Step 411: Robot moved to: (7, 8), observed: occupied Step 412: Robot moved to: (6, 8), observed: free Step 413: Robot moved to: (7, 8), observed: occupied Step 414: Robot moved to: (7, 9), observed: free Step 415: Robot moved to: (7, 8), observed: occupied Step 416: Robot moved to: (7, 7), observed: occupied Step 417: Robot moved to: (7, 6), observed: free Step 418: Robot moved to: (7, 7), observed: occupied Step 419: Robot moved to: (8, 7), observed: free Step 420: Robot moved to: (7, 7), observed: occupied Step 421: Robot moved to: (8, 7), observed: free Step 422: Robot moved to: (9, 7), observed: free Step 423: Robot moved to: (9, 8), observed: free Step 424: Robot moved to: (8, 8), observed: free Step 425: Robot moved to: (7, 8), observed: occupied Step 426: Robot moved to: (6, 8), observed: free Step 427: Robot moved to: (5, 8), observed: free Step 428: Robot moved to: (5, 9), observed: free Step 429: Robot moved to: (4, 9), observed: free Step 430: Robot moved to: (5, 9), observed: free Step 431: Robot moved to: (4, 9), observed: free Step 432: Robot moved to: (4, 8), observed: occupied Step 433: Robot moved to: (4, 9), observed: free Step 434: Robot moved to: (3, 9), observed: free Step 435: Robot moved to: (3, 10), observed: free Step 436: Robot moved to: (3, 9), observed: free Step 437: Robot moved to: (2, 9), observed: free Step 438: Robot moved to: (3, 9), observed: free Step 439: Robot moved to: (3, 10), observed: free Step 440: Robot moved to: (3, 9), observed: free Step 441: Robot moved to: (4, 9), observed: free Step 442: Robot moved to: (4, 10), observed: free Step 443: Robot moved to: (3, 10), observed: free Step 444: Robot moved to: (3, 9), observed: free Step 445: Robot moved to: (2, 9), observed: free Step 446: Robot moved to: (2, 8), observed: free Step 447: Robot moved to: (2, 9), observed: free Step 448: Robot moved to: (2, 8), observed: free Step 449: Robot moved to: (1, 8), observed: free Step 450: Robot moved to: (2, 8), observed: free Step 451: Robot moved to: (2, 9), observed: free Step 452: Robot moved to: (1, 9), observed: occupied Step 453: Robot moved to: (1, 10), observed: occupied Step 454: Robot moved to: (2, 10), observed: occupied Step 455: Robot moved to: (3, 10), observed: free Step 456: Robot moved to: (3, 9), observed: free Step 457: Robot moved to: (2, 9), observed: free Step 458: Robot moved to: (1, 9), observed: occupied Step 459: Robot moved to: (1, 8), observed: free Step 460: Robot moved to: (1, 7), observed: free Step 461: Robot moved to: (1, 6), observed: free Step 462: Robot moved to: (1, 5), observed: free Step 463: Robot moved to: (1, 4), observed: free Step 464: Robot moved to: (2, 4), observed: free Step 465: Robot moved to: (2, 3), observed: free Step 466: Robot moved to: (2, 4), observed: free Step 467: Robot moved to: (1, 4), observed: free Step 468: Robot moved to: (1, 5), observed: free Step 469: Robot moved to: (1, 4), observed: free Step 470: Robot moved to: (1, 5), observed: free Step 471: Robot moved to: (2, 5), observed: occupied Step 472: Robot moved to: (2, 6), observed: free Step 473: Robot moved to: (2, 7), observed: free Step 474: Robot moved to: (3, 7), observed: free Step 475: Robot moved to: (2, 7), observed: free Step 476: Robot moved to: (2, 8), observed: free Step 477: Robot moved to: (2, 7), observed: free Step 478: Robot moved to: (1, 7), observed: free Step 479: Robot moved to: (1, 8), observed: free Step 480: Robot moved to: (1, 7), observed: free Step 481: Robot moved to: (2, 7), observed: free Step 482: Robot moved to: (1, 7), observed: free Step 483: Robot moved to: (1, 8), observed: free Step 484: Robot moved to: (2, 8), observed: free Step 485: Robot moved to: (1, 8), observed: free Step 486: Robot moved to: (1, 7), observed: free Step 487: Robot moved to: (2, 7), observed: free Step 488: Robot moved to: (1, 7), observed: free Step 489: Robot moved to: (2, 7), observed: free Step 490: Robot moved to: (2, 6), observed: free Step 491: Robot moved to: (2, 5), observed: occupied Step 492: Robot moved to: (2, 6), observed: free Step 493: Robot moved to: (1, 6), observed: free Step 494: Robot moved to: (1, 5), observed: free Step 495: Robot moved to: (1, 4), observed: free Step 496: Robot moved to: (1, 3), observed: free Step 497: Robot moved to: (2, 3), observed: free Step 498: Robot moved to: (3, 3), observed: free Step 499: Robot moved to: (2, 3), observed: free Step 500: Robot moved to: (2, 2), observed: free Step 501: Robot moved to: (1, 2), observed: occupied Step 502: Robot moved to: (1, 3), observed: free Step 503: Robot moved to: (2, 3), observed: free Step 504: Robot moved to: (2, 4), observed: free Step 505: Robot moved to: (2, 3), observed: free Step 506: Robot moved to: (3, 3), observed: free Step 507: Robot moved to: (2, 3), observed: free Step 508: Robot moved to: (2, 4), observed: free Step 509: Robot moved to: (1, 4), observed: free Step 510: Robot moved to: (1, 5), observed: free Step 511: Robot moved to: (1, 6), observed: free Step 512: Robot moved to: (2, 6), observed: free Step 513: Robot moved to: (2, 7), observed: free Step 514: Robot moved to: (2, 6), observed: free Step 515: Robot moved to: (2, 5), observed: occupied Step 516: Robot moved to: (1, 5), observed: free Step 517: Robot moved to: (2, 5), observed: occupied Step 518: Robot moved to: (3, 5), observed: free Step 519: Robot moved to: (3, 6), observed: free Step 520: Robot moved to: (2, 6), observed: free Step 521: Robot moved to: (2, 7), observed: free Step 522: Robot moved to: (1, 7), observed: free Step 523: Robot moved to: (1, 6), observed: free Step 524: Robot moved to: (1, 5), observed: free Step 525: Robot moved to: (2, 5), observed: occupied Step 526: Robot moved to: (1, 5), observed: free Step 527: Robot moved to: (2, 5), observed: occupied Step 528: Robot moved to: (2, 4), observed: free Step 529: Robot moved to: (2, 3), observed: free Step 530: Robot moved to: (1, 3), observed: free Step 531: Robot moved to: (2, 3), observed: free Step 532: Robot moved to: (2, 2), observed: free Step 533: Robot moved to: (1, 2), observed: occupied Step 534: Robot moved to: (1, 1), observed: occupied Step 535: Robot moved to: (2, 1), observed: occupied Step 536: Robot moved to: (1, 1), observed: occupied Step 537: Robot moved to: (1, 2), observed: occupied Step 538: Robot moved to: (1, 3), observed: free Step 539: Robot moved to: (2, 3), observed: free Step 540: Robot moved to: (2, 2), observed: free Step 541: Robot moved to: (1, 2), observed: occupied Step 542: Robot moved to: (1, 3), observed: free Step 543: Robot moved to: (1, 4), observed: free Step 544: Robot moved to: (1, 5), observed: free Step 545: Robot moved to: (1, 6), observed: free Step 546: Robot moved to: (1, 7), observed: free Step 547: Robot moved to: (2, 7), observed: free Step 548: Robot moved to: (2, 6), observed: free Step 549: Robot moved to: (3, 6), observed: free Step 550: Robot moved to: (2, 6), observed: free Step 551: Robot moved to: (2, 5), observed: occupied Step 552: Robot moved to: (2, 6), observed: free Step 553: Robot moved to: (1, 6), observed: free Step 554: Robot moved to: (1, 5), observed: free Step 555: Robot moved to: (1, 6), observed: free Step 556: Robot moved to: (1, 7), observed: free Step 557: Robot moved to: (1, 8), observed: free Step 558: Robot moved to: (1, 7), observed: free Step 559: Robot moved to: (1, 8), observed: free Step 560: Robot moved to: (1, 9), observed: occupied Step 561: Robot moved to: (1, 10), observed: occupied Step 562: Robot moved to: (1, 9), observed: occupied Step 563: Robot moved to: (1, 8), observed: free Step 564: Robot moved to: (1, 9), observed: occupied Step 565: Robot moved to: (2, 9), observed: free Step 566: Robot moved to: (3, 9), observed: free Step 567: Robot moved to: (3, 10), observed: free Step 568: Robot moved to: (3, 9), observed: free Step 569: Robot moved to: (3, 8), observed: free Step 570: Robot moved to: (3, 7), observed: free Step 571: Robot moved to: (4, 7), observed: occupied Step 572: Robot moved to: (4, 8), observed: occupied Step 573: Robot moved to: (4, 7), observed: occupied Step 574: Robot moved to: (4, 8), observed: occupied Step 575: Robot moved to: (3, 8), observed: free Step 576: Robot moved to: (3, 9), observed: free Step 577: Robot moved to: (2, 9), observed: free Step 578: Robot moved to: (2, 8), observed: free Step 579: Robot moved to: (1, 8), observed: free Step 580: Robot moved to: (1, 9), observed: occupied Step 581: Robot moved to: (1, 8), observed: free Step 582: Robot moved to: (1, 9), observed: occupied Step 583: Robot moved to: (1, 10), observed: occupied Step 584: Robot moved to: (1, 9), observed: occupied Step 585: Robot moved to: (1, 10), observed: occupied Step 586: Robot moved to: (2, 10), observed: occupied Step 587: Robot moved to: (3, 10), observed: free Step 588: Robot moved to: (3, 9), observed: free Step 589: Robot moved to: (3, 10), observed: free Step 590: Robot moved to: (2, 10), observed: occupied Step 591: Robot moved to: (1, 10), observed: occupied Step 592: Robot moved to: (2, 10), observed: occupied Step 593: Robot moved to: (1, 10), observed: occupied Step 594: Robot moved to: (2, 10), observed: occupied Step 595: Robot moved to: (2, 9), observed: free Step 596: Robot moved to: (1, 9), observed: occupied Step 597: Robot moved to: (2, 9), observed: free Step 598: Robot moved to: (2, 10), observed: occupied Step 599: Robot moved to: (1, 10), observed: occupied Step 600: Robot moved to: (2, 10), observed: occupied Step 601: Robot moved to: (3, 10), observed: free Step 602: Robot moved to: (2, 10), observed: occupied Step 603: Robot moved to: (3, 10), observed: free Step 604: Robot moved to: (4, 10), observed: free Step 605: Robot moved to: (5, 10), observed: free Step 606: Robot moved to: (6, 10), observed: free Step 607: Robot moved to: (5, 10), observed: free Step 608: Robot moved to: (4, 10), observed: free Step 609: Robot moved to: (5, 10), observed: free Step 610: Robot moved to: (6, 10), observed: free Step 611: Robot moved to: (6, 9), observed: free Step 612: Robot moved to: (5, 9), observed: free Step 613: Robot moved to: (6, 9), observed: free Step 614: Robot moved to: (7, 9), observed: free Step 615: Robot moved to: (6, 9), observed: free Step 616: Robot moved to: (5, 9), observed: free Step 617: Robot moved to: (5, 8), observed: free Step 618: Robot moved to: (4, 8), observed: occupied Step 619: Robot moved to: (3, 8), observed: free Step 620: Robot moved to: (4, 8), observed: occupied Step 621: Robot moved to: (4, 7), observed: occupied Step 622: Robot moved to: (4, 6), observed: free Step 623: Robot moved to: (5, 6), observed: free Step 624: Robot moved to: (4, 6), observed: free Step 625: Robot moved to: (4, 5), observed: free Step 626: Robot moved to: (3, 5), observed: free Step 627: Robot moved to: (4, 5), observed: free Step 628: Robot moved to: (4, 6), observed: free Step 629: Robot moved to: (4, 7), observed: occupied Step 630: Robot moved to: (4, 8), observed: occupied Step 631: Robot moved to: (4, 9), observed: free Step 632: Robot moved to: (5, 9), observed: free Step 633: Robot moved to: (5, 8), observed: free Step 634: Robot moved to: (5, 9), observed: free Step 635: Robot moved to: (5, 10), observed: free Step 636: Robot moved to: (4, 10), observed: free Step 637: Robot moved to: (4, 9), observed: free Step 638: Robot moved to: (3, 9), observed: free Step 639: Robot moved to: (3, 10), observed: free Step 640: Robot moved to: (4, 10), observed: free Step 641: Robot moved to: (5, 10), observed: free Step 642: Robot moved to: (6, 10), observed: free Step 643: Robot moved to: (6, 9), observed: free Step 644: Robot moved to: (5, 9), observed: free Step 645: Robot moved to: (4, 9), observed: free Step 646: Robot moved to: (4, 10), observed: free Step 647: Robot moved to: (3, 10), observed: free Step 648: Robot moved to: (4, 10), observed: free Step 649: Robot moved to: (3, 10), observed: free Step 650: Robot moved to: (2, 10), observed: occupied Step 651: Robot moved to: (1, 10), observed: occupied Step 652: Robot moved to: (2, 10), observed: occupied Step 653: Robot moved to: (3, 10), observed: free Step 654: Robot moved to: (4, 10), observed: free Step 655: Robot moved to: (3, 10), observed: free Step 656: Robot moved to: (2, 10), observed: occupied Step 657: Robot moved to: (3, 10), observed: free Step 658: Robot moved to: (2, 10), observed: occupied Step 659: Robot moved to: (1, 10), observed: occupied Step 660: Robot moved to: (1, 9), observed: occupied Step 661: Robot moved to: (1, 8), observed: free Step 662: Robot moved to: (1, 7), observed: free Step 663: Robot moved to: (2, 7), observed: free Step 664: Robot moved to: (2, 8), observed: free Step 665: Robot moved to: (1, 8), observed: free Step 666: Robot moved to: (1, 7), observed: free Step 667: Robot moved to: (2, 7), observed: free Step 668: Robot moved to: (1, 7), observed: free Step 669: Robot moved to: (1, 6), observed: free Step 670: Robot moved to: (1, 7), observed: free Step 671: Robot moved to: (1, 6), observed: free Step 672: Robot moved to: (1, 5), observed: free Step 673: Robot moved to: (1, 6), observed: free Step 674: Robot moved to: (2, 6), observed: free Step 675: Robot moved to: (3, 6), observed: free Step 676: Robot moved to: (3, 7), observed: free Step 677: Robot moved to: (3, 8), observed: free Step 678: Robot moved to: (3, 9), observed: free Step 679: Robot moved to: (3, 10), observed: free Step 680: Robot moved to: (4, 10), observed: free Step 681: Robot moved to: (5, 10), observed: free Step 682: Robot moved to: (5, 9), observed: free Step 683: Robot moved to: (5, 8), observed: free Step 684: Robot moved to: (6, 8), observed: free Step 685: Robot moved to: (6, 9), observed: free Step 686: Robot moved to: (6, 8), observed: free Step 687: Robot moved to: (5, 8), observed: free Step 688: Robot moved to: (5, 7), observed: free Step 689: Robot moved to: (4, 7), observed: occupied Step 690: Robot moved to: (3, 7), observed: free Step 691: Robot moved to: (3, 8), observed: free Step 692: Robot moved to: (3, 9), observed: free Step 693: Robot moved to: (2, 9), observed: free Step 694: Robot moved to: (2, 8), observed: free Step 695: Robot moved to: (1, 8), observed: free Step 696: Robot moved to: (1, 7), observed: free Step 697: Robot moved to: (2, 7), observed: free Step 698: Robot moved to: (1, 7), observed: free Step 699: Robot moved to: (2, 7), observed: free Step 700: Robot moved to: (2, 6), observed: free Step 701: Robot moved to: (1, 6), observed: free Step 702: Robot moved to: (2, 6), observed: free Step 703: Robot moved to: (2, 7), observed: free Step 704: Robot moved to: (2, 6), observed: free Step 705: Robot moved to: (1, 6), observed: free Step 706: Robot moved to: (1, 5), observed: free Step 707: Robot moved to: (1, 6), observed: free Step 708: Robot moved to: (1, 7), observed: free Step 709: Robot moved to: (1, 8), observed: free Step 710: Robot moved to: (1, 9), observed: occupied Step 711: Robot moved to: (1, 8), observed: free Step 712: Robot moved to: (2, 8), observed: free Step 713: Robot moved to: (2, 9), observed: free Step 714: Robot moved to: (3, 9), observed: free Step 715: Robot moved to: (2, 9), observed: free Step 716: Robot moved to: (1, 9), observed: occupied Step 717: Robot moved to: (1, 8), observed: free Step 718: Robot moved to: (2, 8), observed: free Step 719: Robot moved to: (3, 8), observed: free Step 720: Robot moved to: (3, 7), observed: free Step 721: Robot moved to: (3, 6), observed: free Step 722: Robot moved to: (3, 7), observed: free Step 723: Robot moved to: (3, 8), observed: free Step 724: Robot moved to: (3, 9), observed: free Step 725: Robot moved to: (4, 9), observed: free Step 726: Robot moved to: (3, 9), observed: free Step 727: Robot moved to: (2, 9), observed: free Step 728: Robot moved to: (2, 10), observed: occupied Step 729: Robot moved to: (1, 10), observed: occupied Step 730: Robot moved to: (2, 10), observed: occupied Step 731: Robot moved to: (1, 10), observed: occupied Step 732: Robot moved to: (1, 9), observed: occupied Step 733: Robot moved to: (1, 10), observed: occupied Step 734: Robot moved to: (1, 9), observed: occupied Step 735: Robot moved to: (1, 10), observed: occupied Step 736: Robot moved to: (2, 10), observed: occupied Step 737: Robot moved to: (1, 10), observed: occupied Step 738: Robot moved to: (2, 10), observed: occupied Step 739: Robot moved to: (2, 9), observed: free Step 740: Robot moved to: (1, 9), observed: occupied Step 741: Robot moved to: (2, 9), observed: free Step 742: Robot moved to: (1, 9), observed: occupied Step 743: Robot moved to: (2, 9), observed: free Step 744: Robot moved to: (2, 8), observed: free Step 745: Robot moved to: (3, 8), observed: free Step 746: Robot moved to: (3, 7), observed: free Step 747: Robot moved to: (3, 8), observed: free Step 748: Robot moved to: (3, 7), observed: free Step 749: Robot moved to: (3, 8), observed: free Step 750: Robot moved to: (2, 8), observed: free Step 751: Robot moved to: (3, 8), observed: free Step 752: Robot moved to: (3, 7), observed: free Step 753: Robot moved to: (3, 8), observed: free Step 754: Robot moved to: (4, 8), observed: occupied Step 755: Robot moved to: (4, 9), observed: free Step 756: Robot moved to: (4, 8), observed: occupied Step 757: Robot moved to: (5, 8), observed: free Step 758: Robot moved to: (4, 8), observed: occupied Step 759: Robot moved to: (3, 8), observed: free Step 760: Robot moved to: (3, 9), observed: free Step 761: Robot moved to: (4, 9), observed: free Step 762: Robot moved to: (5, 9), observed: free Step 763: Robot moved to: (6, 9), observed: free Step 764: Robot moved to: (7, 9), observed: free Step 765: Robot moved to: (7, 10), observed: free Step 766: Robot moved to: (6, 10), observed: free Step 767: Robot moved to: (7, 10), observed: free Step 768: Robot moved to: (6, 10), observed: free Step 769: Robot moved to: (7, 10), observed: free Step 770: Robot moved to: (8, 10), observed: free Step 771: Robot moved to: (9, 10), observed: occupied Step 772: Robot moved to: (8, 10), observed: free Step 773: Robot moved to: (7, 10), observed: free Step 774: Robot moved to: (8, 10), observed: free Step 775: Robot moved to: (7, 10), observed: free Step 776: Robot moved to: (6, 10), observed: free Step 777: Robot moved to: (7, 10), observed: free Step 778: Robot moved to: (6, 10), observed: free Step 779: Robot moved to: (6, 9), observed: free Step 780: Robot moved to: (5, 9), observed: free Step 781: Robot moved to: (4, 9), observed: free Step 782: Robot moved to: (3, 9), observed: free Step 783: Robot moved to: (4, 9), observed: free Step 784: Robot moved to: (4, 8), observed: occupied Step 785: Robot moved to: (3, 8), observed: free Step 786: Robot moved to: (2, 8), observed: free Step 787: Robot moved to: (1, 8), observed: free Step 788: Robot moved to: (1, 9), observed: occupied Step 789: Robot moved to: (2, 9), observed: free Step 790: Robot moved to: (1, 9), observed: occupied Step 791: Robot moved to: (2, 9), observed: free Step 792: Robot moved to: (3, 9), observed: free Step 793: Robot moved to: (3, 10), observed: free Step 794: Robot moved to: (3, 9), observed: free Step 795: Robot moved to: (3, 10), observed: free Step 796: Robot moved to: (3, 9), observed: free Step 797: Robot moved to: (3, 10), observed: free Step 798: Robot moved to: (2, 10), observed: occupied Step 799: Robot moved to: (2, 9), observed: free Step 800: Robot moved to: (3, 9), observed: free Step 801: Robot moved to: (2, 9), observed: free Step 802: Robot moved to: (2, 8), observed: free Step 803: Robot moved to: (2, 7), observed: free Step 804: Robot moved to: (1, 7), observed: free Step 805: Robot moved to: (1, 8), observed: free Step 806: Robot moved to: (1, 9), observed: occupied Step 807: Robot moved to: (1, 8), observed: free Step 808: Robot moved to: (1, 9), observed: occupied Step 809: Robot moved to: (1, 8), observed: free Step 810: Robot moved to: (1, 9), observed: occupied Step 811: Robot moved to: (1, 10), observed: occupied Step 812: Robot moved to: (1, 9), observed: occupied Step 813: Robot moved to: (1, 10), observed: occupied Step 814: Robot moved to: (2, 10), observed: occupied Step 815: Robot moved to: (2, 9), observed: free Step 816: Robot moved to: (3, 9), observed: free Step 817: Robot moved to: (3, 10), observed: free Step 818: Robot moved to: (2, 10), observed: occupied Step 819: Robot moved to: (3, 10), observed: free Step 820: Robot moved to: (2, 10), observed: occupied Step 821: Robot moved to: (3, 10), observed: free Step 822: Robot moved to: (4, 10), observed: free Step 823: Robot moved to: (3, 10), observed: free Step 824: Robot moved to: (3, 9), observed: free Step 825: Robot moved to: (4, 9), observed: free Step 826: Robot moved to: (5, 9), observed: free Step 827: Robot moved to: (4, 9), observed: free Step 828: Robot moved to: (5, 9), observed: free Step 829: Robot moved to: (5, 10), observed: free Step 830: Robot moved to: (6, 10), observed: free Step 831: Robot moved to: (5, 10), observed: free Step 832: Robot moved to: (6, 10), observed: free Step 833: Robot moved to: (7, 10), observed: free Step 834: Robot moved to: (6, 10), observed: free Step 835: Robot moved to: (7, 10), observed: free Step 836: Robot moved to: (8, 10), observed: free Step 837: Robot moved to: (7, 10), observed: free Step 838: Robot moved to: (8, 10), observed: free Step 839: Robot moved to: (7, 10), observed: free Step 840: Robot moved to: (6, 10), observed: free Step 841: Robot moved to: (5, 10), observed: free Step 842: Robot moved to: (5, 9), observed: free Step 843: Robot moved to: (4, 9), observed: free Step 844: Robot moved to: (3, 9), observed: free Step 845: Robot moved to: (4, 9), observed: free Step 846: Robot moved to: (3, 9), observed: free Step 847: Robot moved to: (3, 8), observed: free Step 848: Robot moved to: (3, 9), observed: free Step 849: Robot moved to: (2, 9), observed: free Step 850: Robot moved to: (3, 9), observed: free Step 851: Robot moved to: (2, 9), observed: free Step 852: Robot moved to: (2, 10), observed: occupied Step 853: Robot moved to: (1, 10), observed: occupied Step 854: Robot moved to: (2, 10), observed: occupied Step 855: Robot moved to: (1, 10), observed: occupied Step 856: Robot moved to: (1, 9), observed: occupied Step 857: Robot moved to: (2, 9), observed: free Step 858: Robot moved to: (2, 10), observed: occupied Step 859: Robot moved to: (3, 10), observed: free Step 860: Robot moved to: (4, 10), observed: free Step 861: Robot moved to: (4, 9), observed: free Step 862: Robot moved to: (4, 8), observed: occupied Step 863: Robot moved to: (4, 7), observed: occupied Step 864: Robot moved to: (5, 7), observed: free Step 865: Robot moved to: (5, 8), observed: free Step 866: Robot moved to: (4, 8), observed: occupied Step 867: Robot moved to: (4, 9), observed: free Step 868: Robot moved to: (4, 8), observed: occupied Step 869: Robot moved to: (5, 8), observed: free Step 870: Robot moved to: (4, 8), observed: occupied Step 871: Robot moved to: (3, 8), observed: free Step 872: Robot moved to: (2, 8), observed: free Step 873: Robot moved to: (2, 9), observed: free Step 874: Robot moved to: (3, 9), observed: free Step 875: Robot moved to: (3, 10), observed: free Step 876: Robot moved to: (3, 9), observed: free Step 877: Robot moved to: (2, 9), observed: free Step 878: Robot moved to: (3, 9), observed: free Step 879: Robot moved to: (4, 9), observed: free Step 880: Robot moved to: (5, 9), observed: free Step 881: Robot moved to: (5, 8), observed: free Step 882: Robot moved to: (4, 8), observed: occupied Step 883: Robot moved to: (4, 7), observed: occupied Step 884: Robot moved to: (3, 7), observed: free Step 885: Robot moved to: (3, 8), observed: free Step 886: Robot moved to: (4, 8), observed: occupied Step 887: Robot moved to: (4, 7), observed: occupied Step 888: Robot moved to: (3, 7), observed: free Step 889: Robot moved to: (3, 6), observed: free Step 890: Robot moved to: (3, 5), observed: free Step 891: Robot moved to: (3, 6), observed: free Step 892: Robot moved to: (3, 7), observed: free Step 893: Robot moved to: (3, 8), observed: free Step 894: Robot moved to: (2, 8), observed: free Step 895: Robot moved to: (2, 7), observed: free Step 896: Robot moved to: (3, 7), observed: free Step 897: Robot moved to: (3, 8), observed: free Step 898: Robot moved to: (3, 9), observed: free Step 899: Robot moved to: (2, 9), observed: free Step 900: Robot moved to: (2, 10), observed: occupied Step 901: Robot moved to: (2, 9), observed: free Step 902: Robot moved to: (2, 10), observed: occupied Step 903: Robot moved to: (3, 10), observed: free Step 904: Robot moved to: (4, 10), observed: free Step 905: Robot moved to: (3, 10), observed: free Step 906: Robot moved to: (4, 10), observed: free Step 907: Robot moved to: (4, 9), observed: free Step 908: Robot moved to: (3, 9), observed: free Step 909: Robot moved to: (3, 10), observed: free Step 910: Robot moved to: (2, 10), observed: occupied Step 911: Robot moved to: (3, 10), observed: free Step 912: Robot moved to: (2, 10), observed: occupied Step 913: Robot moved to: (2, 9), observed: free Step 914: Robot moved to: (2, 10), observed: occupied Step 915: Robot moved to: (2, 9), observed: free Step 916: Robot moved to: (2, 10), observed: occupied Step 917: Robot moved to: (2, 9), observed: free Step 918: Robot moved to: (2, 10), observed: occupied Step 919: Robot moved to: (2, 9), observed: free Step 920: Robot moved to: (3, 9), observed: free Step 921: Robot moved to: (2, 9), observed: free Step 922: Robot moved to: (2, 8), observed: free Step 923: Robot moved to: (2, 9), observed: free Step 924: Robot moved to: (2, 10), observed: occupied Step 925: Robot moved to: (1, 10), observed: occupied Step 926: Robot moved to: (2, 10), observed: occupied Step 927: Robot moved to: (1, 10), observed: occupied Step 928: Robot moved to: (2, 10), observed: occupied Step 929: Robot moved to: (2, 9), observed: free Step 930: Robot moved to: (1, 9), observed: occupied Step 931: Robot moved to: (1, 10), observed: occupied Step 932: Robot moved to: (1, 9), observed: occupied Step 933: Robot moved to: (1, 10), observed: occupied Step 934: Robot moved to: (2, 10), observed: occupied Step 935: Robot moved to: (2, 9), observed: free Step 936: Robot moved to: (2, 10), observed: occupied Step 937: Robot moved to: (1, 10), observed: occupied Step 938: Robot moved to: (1, 9), observed: occupied Step 939: Robot moved to: (1, 8), observed: free Step 940: Robot moved to: (1, 9), observed: occupied Step 941: Robot moved to: (1, 8), observed: free Step 942: Robot moved to: (2, 8), observed: free Step 943: Robot moved to: (3, 8), observed: free Step 944: Robot moved to: (3, 9), observed: free Step 945: Robot moved to: (2, 9), observed: free Step 946: Robot moved to: (3, 9), observed: free Step 947: Robot moved to: (3, 10), observed: free Step 948: Robot moved to: (3, 9), observed: free Step 949: Robot moved to: (3, 8), observed: free Step 950: Robot moved to: (3, 9), observed: free Step 951: Robot moved to: (2, 9), observed: free Step 952: Robot moved to: (3, 9), observed: free Step 953: Robot moved to: (2, 9), observed: free Step 954: Robot moved to: (2, 8), observed: free Step 955: Robot moved to: (2, 7), observed: free Step 956: Robot moved to: (2, 6), observed: free Step 957: Robot moved to: (2, 7), observed: free Step 958: Robot moved to: (2, 6), observed: free Step 959: Robot moved to: (1, 6), observed: free Step 960: Robot moved to: (1, 7), observed: free Step 961: Robot moved to: (1, 6), observed: free Step 962: Robot moved to: (1, 7), observed: free Step 963: Robot moved to: (1, 8), observed: free Step 964: Robot moved to: (1, 9), observed: occupied Step 965: Robot moved to: (2, 9), observed: free Step 966: Robot moved to: (1, 9), observed: occupied Step 967: Robot moved to: (1, 10), observed: occupied Step 968: Robot moved to: (1, 9), observed: occupied Step 969: Robot moved to: (1, 10), observed: occupied Step 970: Robot moved to: (1, 9), observed: occupied Step 971: Robot moved to: (1, 10), observed: occupied Step 972: Robot moved to: (2, 10), observed: occupied Step 973: Robot moved to: (3, 10), observed: free Step 974: Robot moved to: (4, 10), observed: free Step 975: Robot moved to: (3, 10), observed: free Step 976: Robot moved to: (3, 9), observed: free Step 977: Robot moved to: (3, 10), observed: free Step 978: Robot moved to: (4, 10), observed: free Step 979: Robot moved to: (3, 10), observed: free Step 980: Robot moved to: (2, 10), observed: occupied Step 981: Robot moved to: (2, 9), observed: free Step 982: Robot moved to: (2, 8), observed: free Step 983: Robot moved to: (2, 9), observed: free Step 984: Robot moved to: (3, 9), observed: free Step 985: Robot moved to: (3, 8), observed: free Step 986: Robot moved to: (3, 7), observed: free Step 987: Robot moved to: (3, 6), observed: free Step 988: Robot moved to: (4, 6), observed: free Step 989: Robot moved to: (4, 7), observed: occupied Step 990: Robot moved to: (4, 8), observed: occupied Step 991: Robot moved to: (4, 9), observed: free Step 992: Robot moved to: (5, 9), observed: free Step 993: Robot moved to: (6, 9), observed: free Step 994: Robot moved to: (6, 8), observed: free Step 995: Robot moved to: (6, 7), observed: free Step 996: Robot moved to: (5, 7), observed: free Step 997: Robot moved to: (5, 6), observed: free Step 998: Robot moved to: (5, 7), observed: free Step 999: Robot moved to: (5, 6), observed: free Step 1000: Robot moved to: (6, 6), observed: free
In [19]:
gif(anim, "./assets/occupancy_grid_mapping.gif")
[ Info: Saved animation to D:\ANPL\0970252-pomdp\Tutorials\assets\occupancy_grid_mapping.gif
Out[19]:
Using Julia¶
In this course we will use Julia for our code examples and implementations, and we encourage you to implement your homework in Julia as well.
To run this tutorial locally via VSCode you need to make sure you have Julia installed on your computer.
Installing Julia: Follow this guide or this guide to install Julia on your computer.
VSCode: To run the tutorial in VSCode:
To run this tutorial in Google Colab you can upload it to colab (upload the contents of assets directory as well), set the runtime type to Julia and use a CPU, then run the tutorial.
We encourage you to work in VSCode directly, get familiar with Julia and implement your homework in .jl files, which allows a better debugging environment.
For more information about Julia please refer to the following sources:
Credits